// package wtx.leetcode;

// import java.util.ArrayList;
// import java.util.Collections;
// import java.util.HashSet;
// import java.util.List;
// import java.util.Set;
// import java.util.Random;
// /**
//  * Given an array nums of n integers, are there elements a, b, c in nums such
//  * that a + b + c = 0 ? Find all unique triplets in the array which gives the sum
//  * of zero.
//  * 
//  * Note:
//  * 
//  * The solution set must not contain duplicate triplets.
//  * 
//  * Example:
//  * 
//  * Given array nums = [-1, 0, 1, 2, -1, -4],
//  * 
//  * A solution set is: [ 
//  *        [-1, 0, 1], 
//  *        [-1, -1, 2] 
//  * ]
//  * 
//  *  first sort:
//  *   [-4, -1, -1, 0, 1, 2]
//  *  start from first two element: 
//  *     init: first = 0, second = 1, last = 5
//  *     sum(0, second) is the smallest sum, so the 3rd element must lie at the last, 
//  *      start from last, 
//  *        if sum(first, second, last) == 0, we find a tuple, if this is not recored before, record it;
//  *        else: change second = second + 1
//  *        finally: last --,
//  *        if second >= last: first = first + 1
//  *        if first >= last: end
//  *
//  *  solution2:
//  *    tripCache = set[long]
//  *    for first in 0 ... last-1:
//  *      for second in first+1 ... last:
//  *        key = {first, second}
//  *        cache.add[sum, {key, (first, second)}]
//  *    for i in 0 ... last:
//  *      int target = -nums[i]
//  *      if target in cache:
//  *        for key in cacke[target]:
//  *          if key not in tripCache:
//  *            ret.add({nums[i], }) 
//  */
// class Solution0 {
//   private static long LONG_MASK = 0x00000000ffffffffl;
//   private int binarySearch(List<Integer> input, int target, int left, int right) {
//     if (right - left <= 1) {
//       return left;
//     }
//     // if (right - left == 2) {
//     //   if (input.get(left) == target) {
//     //     return left;
//     //   } else if (input.get(left) > target) {
//     //     return left - 1;
//     //   } else {
//     //     return right - 1;
//     //   }
//     // }
//     int mid = (left + right)/2;
//     if (input.get(mid) > target) {
//       return binarySearch(input, target, left, mid);
//     } else if (input.get(mid) < target) {
//       return binarySearch(input, target, mid, right);
//     } else {
//       return mid;
//     }
//   }
//   public List<List<Integer>> threeSum(int[] nums) {
//     List<List<Integer>> ret = new ArrayList<>();
//     if (nums == null || nums.length < 3) {
//       return ret;
//     }
//     List<Integer> input = new ArrayList<>();
//     Set<Long> tripletSet = new HashSet<>();
//     for(int i : nums) {
//       input.add(i);
//     }
//     Collections.sort(input);
//     final int ARY_LEN = nums.length;
//     int first = 0, second = 1, last = ARY_LEN - 1;
//     int last0 = ARY_LEN;
//     for (;first + 1 < last;) {
//       int sum3 = input.get(first) + input.get(second) + input.get(last);
//       if (sum3 == 0) {
//         long key = ((0L | input.get(first)) << 32) | (LONG_MASK & input.get(second));
//         if (!tripletSet.contains(key)) {
//           tripletSet.add(key);
//           List<Integer> tri = new ArrayList<>();
//           tri.add(input.get(first));
//           tri.add(input.get(second));
//           tri.add(input.get(last));
//           ret.add(tri);
//         }
//         if (second == first+1 && last0 == ARY_LEN) {
//           last0 = last;
//         }
//         ++ second;
//       } else if (sum3 < 0) {
//         ++ second;
//       } else {
//         --last;
//       }
//       if (second >= last) {
//         ++ first;
//         second = first + 1;
//         if (second >= last0) break;
//         int target = - input.get(first) - input.get(second);
//         last = binarySearch(input, target, last, last0);
//         last0 = ARY_LEN;
//       }
//     }
//     return ret;
//   }

//   public static void benchMark() {
//     long alltime = 0;
//     long maxtime = 0;
//     int[] maxnums = null;
//     for (int k = 0; k < 5000; ++k) {
//       final int NUM_LEN = 100;
//       final int NUM_BOUND = 100;
//       int[] nums = new int[NUM_LEN];
//       Random rnd = new Random(1234 + k);
//       nums[0] = rnd.nextInt(2 * NUM_BOUND) - NUM_BOUND;
//       System.out.print("[" + nums[0]);
//       for (int i = 1; i < NUM_LEN; ++i) {
//         nums[i] = rnd.nextInt(2 * NUM_BOUND) - NUM_BOUND;
//         if (i < 5) {
//           System.out.print(", " + nums[i]);
//         }
//       }
//       System.out.println("... ]");
//       Solution0 s = new Solution0();
//       List<List<Integer>> ret = s.threeSum(nums);
//       long curt = System.currentTimeMillis();
//       for (int n = 0; n < 100; ++n) {
//         ret = s.threeSum(nums);
//       }
//       long e = System.currentTimeMillis() - curt;
//       alltime += e;
//       if (e > maxtime) {
//         maxtime = e;
//         maxnums = nums;
//       }
//       System.out.println(e + " ms");
//     }
//     System.out.println("\nall eclipse time: " + alltime);
//     System.out.print("[" + maxnums[0]);
//     for (int i = 1; i < maxnums.length; ++i) {
//       System.out.print(", " + maxnums[i]);
//     }
//     System.out.println("]\n eclipse time = " + maxtime);
//   }

//   public static void testOneCase() {
//     // int[] nums = { -4, -2, 1, -5, -4, -4, 4, -2, 0, 4, 0, -2, 3, 1, -5, 0 };
//     // int[] nums = {-1, 0, 1, 0};
//     // int[] nums = {-4, -1, -1, 0, 1, 2};
//     // int[] nums = {-4,-2,-2,-2,0,1,2,2,2,3,3,4,4,6,6};
//     final int NUM_LEN = 100;
//     final int NUM_BOUND = 100;
//     int[] nums = new int[NUM_LEN];
//     Random rnd = new Random(1234 + 9);
//     nums[0] = rnd.nextInt(2 * NUM_BOUND) - NUM_BOUND;
//     System.out.print("[" + nums[0]);
//     for (int i = 1; i < NUM_LEN; ++i) {
//       nums[i] = rnd.nextInt(2 * NUM_BOUND) - NUM_BOUND;
//       if (i < 5) {
//         System.out.print(", " + nums[i]);
//       }
//     }
//     System.out.println("... ]");
//     Solution0 s = new Solution0();
//     List<List<Integer>> ret = s.threeSum(nums);
//     long curt = System.currentTimeMillis();
//     for (int n = 0; n < 100; ++n) {
//       ret = s.threeSum(nums);
//     }
//     long e = System.currentTimeMillis() - curt;
//     System.out.println(e + " ms");
//     // for (List<Integer> tri : ret) {
//     //   System.out.print("[" + tri.get(0));
//     //   for (int i = 1; i < 3; ++i) {
//     //     System.out.print(", " + tri.get(i));
//     //   }
//     //   System.out.println("]");
//     // }
//   }
  
//   public static void main(String[] args) {
//     benchMark();
//     // testOneCase();
//   }
// }